package week02

// 23. 合并K个升序链表
// https://leetcode-cn.com/problems/merge-k-sorted-lists/

// 分治思想
// 1、将数组中的链表两两合并为新的升序链表
// 2、重复此操作，直到剩下一个链表

// 子问题：两个升序链表合并为新的升序链表

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	// 拆分
	var list1 = mergeKLists(lists[:len(lists)/2])
	var list2 = mergeKLists(lists[len(lists)/2:])
	return mergeList(list1, list2)
}

// 递归合并
func mergeList(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}

	var node = &ListNode{}
	if l1.Val > l2.Val {
		node.Next = l2
		node.Next.Next = mergeList(l1, l2.Next)
	} else {
		node.Next = l1
		node.Next.Next = mergeList(l1.Next, l2)
	}
	return node.Next
}

func mergeList2(l1, l2 *ListNode) *ListNode {
	var node = &ListNode{}
	var head = node
	for l1 != nil && l2 != nil {
		if l1.Val > l2.Val {
			head.Next = l2
			l2 = l2.Next
		} else {
			head.Next = l1
			l1 = l1.Next
		}
		head = head.Next
	}
	if l1 != nil {
		head.Next = l1
	}
	if l2 != nil {
		head.Next = l2
	}
	return node.Next
}

type ListNode struct {
	Val int
	Next *ListNode
}
